package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/8 21:31
 */
public class Title399II {

    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        //构建邻接表
        for (int i = 0; i <equations.size() ; i++) {
            List<String> edge = equations.get(i);
            graph.computeIfAbsent(edge.get(0), k -> new HashMap<>()).put(edge.get(1), values[i]);
            graph.computeIfAbsent(edge.get(1), k -> new HashMap<>()).put(edge.get(0), 1 / values[i]);
        }
        double[] result = new double[queries.size()];
        Arrays.fill(result, -1.0);
        for (int i = 0; i < queries.size(); i++) {
            String cur = queries.get(i).get(0);
            String tag = queries.get(i).get(1);
            Set<String> visited = new HashSet<>();
            dfs(graph, result, visited, cur, tag, i, 1.0);
        }
        return result;
    }

    private static void dfs(Map<String, Map<String, Double>> graph, double[] result, Set<String> visited, String cur, String tag, int i, double pre) {
        if (!graph.containsKey(cur) || !graph.containsKey(tag)) {
            return;
        }
        if (cur.equals(tag)) {
            result[i] = pre;
            return;
        }
        visited.add(cur);
        Map<String, Double> edgeValue = graph.get(cur);
        if (edgeValue.containsKey(tag)) {
            result[i] = edgeValue.get(tag) * pre;
            return;
        }
        Set<String> set = edgeValue.keySet();
        for (String edge : set) {
            if (result[i] == -1.0 && !visited.contains(edge)) {
                dfs(graph, result, visited, edge, tag, i, edgeValue.get(edge) * pre);
            }
        }
    }

    public static void main(String[] args) {
        List<List<String>> equation = new ArrayList<>();
        List<String> temp = new ArrayList<>();
        temp.add("a");
        temp.add("b");
        equation.add(new ArrayList<>(temp));
        temp.clear();
        temp.add("b");
        temp.add("c");
        equation.add(temp);
        double[] value = {2.0, 3.0};
        List<List<String>> querys = new ArrayList<>();
        List<String> e = new ArrayList<>();
        e.add("a");
        e.add("c");
        querys.add(new ArrayList<>(e));
        e.clear();
        e.add("b");
        e.add("a");
        querys.add(e);
        calcEquation(equation, value, querys);
    }
}
